
package jweslley.ProblemSetVolumes.VolumeIV;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * http://icpcres.ecs.baylor.edu/onlinejudge/external/4/495.html
 *
 * @author  Jonhnny Weslley
 * @version 1.00, 19/10/2008
 */
public class FibonacciFreeze {

	static List<BigInteger> cache = new ArrayList<BigInteger>();

	public static void main(String[] args) {
		cache.add(new BigInteger("0"));
		cache.add(new BigInteger("1"));

		Scanner in = new Scanner(System.in);
		int n;		
		while (in.hasNext()) {
			n = in.nextInt();
			System.out.printf("The Fibonacci number for %s is %s\n", n, fibonacci(n));
		}
	}

	static Object fibonacci(int n) {
		if (n < cache.size()) {
			return cache.get(n);
		}
		for (int i = cache.size(); i <= n; i++) {
			cache.add(cache.get(i - 1).add(cache.get(i - 2)));
		}
		return cache.get(n);
	}

}
